package dynamic;

/**
 * 题目：求回文子串的个数
 *
 * y: abc 3个
 *    aba  4个
 */
public class solution_1 {
    /**
     * 第一种方法就是暴力破解法使用for循环，时间复杂度为O(n^3),空间复杂度为O(1)
     *
     * 第二种方法：使用一个二维数组来存储子串是否是回文字符串，把结果存下来就是动态规划
     * 的解法，可以节约O(n)的复杂度,是一种空间换时间的概念
     * 从外层到内层依次进行判断字符串，这里节约的时间就是把每次判断是否是回文的状态存储到
     * 数组里面了，这就节约了时间复杂度
     */
    //Time:O(n^2) Space:O(n)
    public static int solution_1(String s){
        if(s==null||s.length()==0)return 0;
        int n=s.length(),count=0;
        boolean[][] d=new boolean[n][n];
        for (int i=n-1;i>=0;--i){//数组下标是从0开始，所以n-1表示的是最后一个字符
            for (int j=i;j<n;j++){
                //这里的判断就是同一个字符串是回文字符串
                if(i==j)d[i][j]=true;
                else {
                    boolean b = s.charAt(i) == s.charAt(j);//判断两个字符是否想等
                    //这里表示的是相邻的字符串的状态
                    if(i+1==j)d[i][j]= b;
                    //这里就是精华部分了
                    /**
                     * 因为我们的循环已经处理好相等的时候，相邻的时候的状态了，这里我们就只需要判断i+1和j-1就行了
                     * 都是依次递进的关系
                     * 比如这里比较abcmda
                     * 在比较b和d两个字符的时候a和a已经比较过了
                     * 在比较c和m的时候ab和da的状态也已经比较好了
                     *
                     */
                    else d[i][j]= b &&d[i+1][j-1];
                }
                if(d[i][j])++count;
            }
        }
        return count;
    }

    /**
     * 第三种方法：
     * 由某个字符向两边扩展进行对比
     *  这种方式比较容易理解
     * 比如比较： abcdef
     * 先比较 a
     * 然后 b  ba
     * 然后 c cb cba
     * 依次遍历完就行
     */
    //Time:O(n^2) Space:O(1)
    public int solution_2(String s){
        if(s==null||s.length()==0)return 0;
        int count=0;
        for (int i = 0; i < s.length(); i++) {
            count+=puStr(s,i,i);
            count+=puStr(s,i,i+1);//以两个数为中心向两边扩展
        }
        return count;
    }
    //求一个字符串回文串的个数
    int puStr(String s,int left , int right){
        int count=0;
        while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
            ++count;
            --left;
            ++right;
        }
        return count;
    }


    public static void main(String[] args) {
        System.out.println(solution_1("abc"));
    }
}
